//给你一个数组 nums 。 
//
// 每次操作你可以选择 nums 中的任意一个元素并将它改成 任意值 。 
//
// 在 执行最多三次移动后 ，返回 nums 中最大值与最小值的最小差值。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [5,3,2,4]
//输出：0
//解释：我们最多可以走 3 步。
//第一步，将 2 变为 3 。 nums 变成 [5,3,3,4] 。
//第二步，将 4 改为 3 。 nums 变成 [5,3,3,3] 。
//第三步，将 5 改为 3 。 nums 变成 [3,3,3,3] 。
//执行 3 次移动后，最小值和最大值之间的差值为 3 - 3 = 0 。 
//
// 示例 2： 
//
// 
//输入：nums = [1,5,0,10,14]
//输出：1
//解释：我们最多可以走 3 步。
//第一步，将 5 改为 0 。 nums变成 [1,0,0,10,14] 。
//第二步，将 10 改为 0 。 nums变成 [1,0,0,0,14] 。
//第三步，将 14 改为 1 。 nums变成 [1,0,0,0,1] 。
//执行 3 步后，最小值和最大值之间的差值为 1 - 0 = 1 。
//可以看出，没有办法可以在 3 步内使差值变为0。
// 
//
// 示例 3： 
//
// 
//输入：nums = [3,100,20]
//输出：0
//解释：我们最多可以走 3 步。
//第一步，将 100 改为 7 。 nums 变成 [3,7,20] 。
//第二步，将 20 改为 7 。 nums 变成 [3,7,7] 。
//第三步，将 3 改为 7 。 nums 变成 [7,7,7] 。
//执行 3 步后，最小值和最大值之间的差值是 7 - 7 = 0。 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁵ 
// -10⁹ <= nums[i] <= 10⁹ 
// 
//
// Related Topics 贪心 数组 排序 👍 59 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.Arrays;

public class MinimumDifferenceBetweenLargestAndSmallestValueInThreeMoves {
    public static void main(String[] args) {
        Solution solution = new MinimumDifferenceBetweenLargestAndSmallestValueInThreeMoves().new Solution();
        System.out.println(solution.minDifference(new int[]{1, 5, 0, 10, 14}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 要么最小值变成变成最大值
         * 要么最大值变成最小值
         * 最多3的平方 9种写法
         *
         * @param nums
         * @return
         */
        public int minDifference(int[] nums) {
//            int n = nums.length;
//            if (n <= 3) {
//                return 0;
//            }
//            Arrays.sort(nums);
//            int min = nums[0];
//            int max = nums[n - 1];
//            int i = 0;
//            int[] arr = new int[9];
//            Arrays.fill(arr, Integer.MAX_VALUE);
//            //0 3
//            arr[i++] = Math.abs(nums[n - 4] - min);
//            arr[i++] = Math.abs(nums[3] - max);
//            //1 2
//            arr[i++] = Math.abs(nums[n - 3] - nums[1]);
//            arr[i++] = Math.abs(nums[n - 2] - nums[2]);
//            int ans = Integer.MAX_VALUE;
//            for (int i1 : arr) {
//                ans = Math.min(ans, i1);
//            }
//            return ans;
            return minDifference(nums,3);
        }

        //如果是最多执行k次呢
        public int minDifference(int[] nums, int k) {
            int n = nums.length;
            if (n <= k) {
                return 0;
            }
            Arrays.sort(nums);
            int windowLength = n-1;
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < k; i++) {
                windowLength -= i;
                for (int j = 0; j+windowLength < n; j++) {
                    ans = Math.min(ans,Math.abs(nums[j]-nums[j+windowLength]));
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}